class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int numEnclaves(vector<vector<int>>& g) {
        int m=g.size();
        int n=g[0].size();
        vector<vector<int>> v(m,vector<int>(n,-1));
        queue<pair<int,int>> q;
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(g[i][j]==0) v[i][j]=0;
                if(g[i][j]==1) v[i][j]=1;

                if(g[i][0]==1) q.push({i,0});
                if(g[i][n-1]==1) q.push({i,n-1});
                if(g[0][j]==1) q.push({0,j});
                if(g[m-1][j]==1) q.push({m-1,j});
            }
        }
        while(q.size())
        {
            int sz=q.size();
            for(int i=0;i<sz;++i)
            {
                auto [x,y]=q.front();
                q.pop();
                v[x][y]=0;
                for(int j=0;j<4;++j)
                {
                    int a=x+dx[j];
                    int b=y+dy[j];
                    if(a>=0&&a<m&&b>=0&&b<n&&v[a][b]==1)
                    {
                        q.push({a,b});
                        v[a][b]=0;
                    }
                }
            }
        }
        int count=0;
        for(int i=1;i<m-1;++i)
        {
            for(int j=1;j<n-1;++j)
            {
                if(v[i][j]==1) count++;
            }
        }
        return count;
    }
};
